/*
	Copyright (c) 2009-2011, Stefan Webb.

	This file is part of SimpleML. Please read the file "license.txt", 
	which contains the conditions under which this software is distributed.
*/

/*!
	\file bucket.h
	\author Stefan Webb
	\brief Definition of the Bucket class template
*/

#ifndef BUCKET_H
#define BUCKET_H

//#include "stdafx.h"

/*! \brief Class to use stack. */
template <class T> class Bucket
{
public:
	/*! \brief Default constructor. */
	Bucket();

	/*! \brief Constructor for bucket with identical initial and minimum capacity.
		\param capacity Initial and minimum capacity of bucket. */
	Bucket(unsigned int capacity);

	/*! \brief Constructor for bucket specifying initial and minimum capacity.
		\param initialSize Initial capacity of bucket. 
		\param minimumSize Minimum capacity of bucket. */
	Bucket(unsigned int initialCapacity, unsigned int minimumCapacity);

	/*! \brief Default destructor for bucket. */
	~Bucket();

	/*! \brief Get element of bucket, without bounds check (for speed).
		\param i Index of element to retrieve.
		\return Element at specified index. */
	T& operator[](unsigned int i);

	/*! \brief Add element to top of bucket.
		\param element Element to add to bucket. */
	void add(T& element);

	/*! \brief Add empty element. */
	void addEmpty();

	/*! \brief Return top element of bucket. */
	T& topElement();

	/*! \brief Push element onto top of bucket.
		\param element Element to push onto bucket. */
	void push(T element);

	/*! \brief Remove topmost element from bucket.
		\return Topmost element of bucket. */
	T& pop();

	/*! \brief Count items in bucket. 
		\return Item count of bucket. */
	unsigned int size();

	/*! \brief Get bucket capacity.
		\return Capacity of bucket. */
	unsigned int capacity();

	/*! \brief Expand bucket size to its capacity. */
	void expand();

	/*! \brief Reset bucket by emptying and resizing to initial capacity. */
	void reset();

	/*! \brief Create new bucket with identical initial and minimum capacity.
		\param capacity Initial and minimum capacity of bucket. */
	void create(unsigned int capacity);

	/*! \brief Create new bucket with given initial and minimum capacity.
		\param initialSize Initial capacity of bucket. 
		\param minimumSize Minimum capacity of bucket. */
	void create(unsigned int initialCapacity, unsigned int minimumCapacity);

	/*! \brief Destroy bucket by freeing memory. */
	void destroy();

	/*! \brief Chucks out the contents of the bucket. */
	void empty();

protected:
	/*! \brief Halve capacity of bucket. Does not check whether items will be lost. */
	void halve();

	/*! \brief Double capacity of bucket. */
	void twofold();

	/*! \brief Resize bucket capacity.
		\param capacity New capacity for bucket. */
	void resize(unsigned int capacity);

	/*! \brief Initialize variables. */
	void initialize();

	/*! \brief Array of stack items. */
	T* array_;

	/*! \brief How full bucket is. */
	unsigned int size_;

	/*! \brief Capacity of bucket. */
	unsigned int capacity_;

	/*! \brief Initial capacity of bucket. */
	unsigned int initialCapacity_;

	/*! \brief Minimum capacity of bucket. */
	unsigned int minimumCapacity_;
};

/* Default constructor. */
template <class T> Bucket<T>::Bucket()
{
	initialize();
}

/* Constructor for bucket specifying initial size. */
template <class T> Bucket<T>::Bucket(unsigned int capacity)
{
	initialize();
	create(capacity);
}

/* Constructor for bucket specifying initial and minimum capacity. */
template <class T> Bucket<T>::Bucket(unsigned int initialCapacity, unsigned int minimumCapacity)
{
	initialize();
	create(initialCapacity, minimumCapacity);
}

/* Default destructor for bucket. */
template <class T> Bucket<T>::~Bucket()
{
	destroy();
}

/* Initialize variables. */
template <class T> void Bucket<T>::initialize()
{
	// Initialize variables
	size_ = 0;
	capacity_ = 0;
	array_ = 0;
	initialCapacity_ = 0;
	minimumCapacity_ = 0;
}

/* Create new bucket with identical initial and minimum capacity. */
template <class T> void Bucket<T>::create(unsigned int capacity)
{
	create(capacity, capacity);
}

/* Create new bucket with given initial and minimum capacity. */
template <class T> void Bucket<T>::create(unsigned int initialCapacity, unsigned int minimumCapacity)
{
	// Make sure initial capacity is not less than minimum capacity
	if (initialCapacity < minimumCapacity) {
		(error << L"Initial capacity of bucket is less than minimum capacity.").warning();
		initialCapacity = minimumCapacity;
	}

	// Delete bucket
	if (array_)
		delete [] array_;

	// Get memory for bucket items
	array_ = new T[initialCapacity];

	// Set capacity and size
	capacity_ = initialCapacity;
	initialCapacity_ = initialCapacity;
	minimumCapacity_ = minimumCapacity;
	size_ = 0;
}

/* Reset bucket. */
template <class T> void Bucket<T>::reset()
{
	// Empty bucket
	empty();

	// Change to initial capacity
	resize(initialCapacity_);
}

/* Chucks out contents of bucket. */
template <class T> void Bucket<T>::empty()
{
	// Empty bucket
	size_ = 0;
}

/* Count items in bucket. */
template <class T> unsigned int Bucket<T>::size()
{
	return size_;
}

/* Get bucket capacity. */
template <class T> unsigned int Bucket<T>::capacity()
{
	return capacity_;
}

/* Expand bucket size to its capacity. */
template <class T> void Bucket<T>::expand()
{
	size_ = capacity_;
}

/* Add element to top of bucket. */
template <class T> void Bucket<T>::add(T& element)
{
	// Double stack if we do not have enough capacity
	if (size_ >= capacity_)
		twofold();

	// Add element
	(*this)[size_++] = element;
}

/* Add empty element to top of bucket. */
template <class T> void Bucket<T>::addEmpty()
{
	// Double stack if we do not have enough capacity
	if (size_ >= capacity_)
		twofold();

	// Add element
	size_++;
}

/* Add empty element to top of bucket. */
template <class T> T& Bucket<T>::topElement()
{
	return array_[size_ - 1];
}

/* Push element onto top of bucket. */
template <class T> void Bucket<T>::push(T element)
{
	add(element);
}
/* Remove element from bucket. */
template <class T> T& Bucket<T>::pop()
{
	// If no elements then return first element
	// I can't think of a good way to do this, you have to return something
	// And with a template, there is no null value for generic types
	if (!size_)
		return (*this)[0];
	
	// If the stack contains less than half the capacity then downsize.
	if (size_ <= capacity_ / 2 && capacity_/2 >= minimumCapacity_)
		halve();

	// Return the last element
	return (*this)[--size_];
}

/* Halve capacity of bucket. Does not check whether items will be lost. */
template <class T> void Bucket<T>::halve()
{
	resize(capacity_ / 2);
}

/* Double capacity of bucket. */
template <class T> void Bucket<T>::twofold()
{
	// If capacity is nonzero then double
	if (capacity_)
		resize(capacity_ * 2);

	// If the capacity is zero then doubling will not work...
	else
		resize(2);
}

/* Resize bucket capacity. */
template <class T> void Bucket<T>::resize(unsigned int capacity)
{
	// Create a temporary array
	T* temp = new T[capacity];
	unsigned int size = min(size_, capacity);
	
	// Copy memory if neccessary
	if (size_)
		memcpy(temp, array_, sizeof(T) * size);

	// Delete bucket and set new bucket
	destroy();
	array_ = temp;
	capacity_ = capacity;
	size_ = size;
}

/* Destroys bucket by freeing memory. */
template <class T> void Bucket<T>::destroy()
{
	// Delete bucket
	if (array_)
		delete [] array_;

	// Initialize variables
	initialize();
}

/* Get element of bucket, without bounds check */
template <class T> T& Bucket<T>::operator[](unsigned int i)
{
	return array_[i];
}

#endif